#include "NodeLinkedList.h"
#define INDEX_INIT_VAL 0 // used to initialize new nodes' index
#define NODE_DUMMY_INIT_VAL 0 // node list's head and tail dummy nodes are initialized with graph node data with this value

//////////////////////////////////////////////////////////////////////////////////// class NodeLinkedList::ListNode's methods

//////////////////////////////////////////////////////////////////// public methods
/***************************************************************************************
* function name: ListNode (Node& nodeData)
* The Input: Graph node data to be set as list node's data attribute
* The output: None
* The Function operation: Initializes graph node data reference to given graph node.
*						  Previous and next list node pointers are initialized as NULL and
*						  index is initialized as INDEX_INIT_VAL because the new list node's
*						  position in the linked list is not set yet
***************************************************************************************/
NodeLinkedList::ListNode::ListNode(Node& nodeData): m_graphNodeData(nodeData) {
	// TODO DEBUG PRINT!!!
	cout << "in ListNode constructor" << endl;
	// new list node is not yet linked to the list
	m_prevListNode = NULL;
	m_nextListNode = NULL;
}

/***************************************************************************************
 * function name: Node(const ListNode& listNodeToCopy)
 * The Input: List node to be copied
 * The output: None
 * The Function operation: Creates a new list node whose data attribute is a copy of given
 * 						   node's. New node's index is set as given node's.
 * 						   Previous/next node attributes are NULL the new node's
 * 						   position the list is not set yet
 ***************************************************************************************/
NodeLinkedList::ListNode::ListNode(const ListNode& listNodeToCopy): m_graphNodeData( *(new Node(listNodeToCopy.m_graphNodeData)) ) {

	// TODO DEBUG PRINT!!!
	cout << "in ListNode COPY constructor" << endl;

	// new list node is not yet linked to the list
	m_prevListNode = NULL;
	m_nextListNode = NULL;
}

/****************************************************************************************
* function name: ~ListNode()
* The Input: None
* The output: None
* The Function operation: Graph node data pointed is set to NULL to prevent deleting pointed
* 						  Node objects. Next and previous list nodes are linked and the
* 						  next list nodes' indices are decremented
***************************************************************************************/
NodeLinkedList::ListNode::~ListNode() {

	// TODO DEBUG PRINT!!!
	cout << "in ListNode destructor" << endl;

	delete &m_graphNodeData; // delete allocated memory for graph node
	// link next node and previous node
	if (m_nextListNode != NULL) { // not end of list
		m_nextListNode->m_prevListNode = m_prevListNode;
	}
	if (m_prevListNode != NULL) { // not beginning of list
		m_prevListNode->m_nextListNode = m_nextListNode;
	}

//	// decrement next list nodes' index
//	ListNode* currListNode = m_nextListNode;
//	while (currListNode != NULL) { // scan list to its end
//		--(currListNode->m_index); // decrement index
//		currListNode = currListNode->m_nextListNode; // move to next node
//	}
}

//////////////////////////////////////////////////////////////////////////////////// class NodeLinkedList's methods

//////////////////////////////////////////////////////////////////// private methods
/***************************************************************************************
* function name: findPlace(const Node& newGraphNode)
* The Input: Pointer to graph node to add
* The output: List node pointer to which the new graph node should be linked.
* 	          If a graph node with new graph node's number already exists, NULL is returned
* The Function operation: Uses 2 list node pointers- one to point at previous list node being
*			              scanned and another one to point at current node on list.
*	                      Method compares current graph node's number with given graph node's
*	                      number.
*			              If numbers are equal, given graph node cannot be added and NULL is
*			              returned. If current graph node's number is smaller than new graph
*			              node's, a pointer to current list node is returned
***************************************************************************************/
NodeLinkedList::ListNode* NodeLinkedList::findPlace(const Node& newGraphNode) const {

	ListNode* after = m_headDummy; // pointer to previous node being scanned
	ListNode* curr = after->m_nextListNode; // pointer to current node being scanned

	while (after->m_nextListNode != m_tailDummy) {

		if (curr->m_graphNodeData == newGraphNode) {
			return NULL; //duplicate graph node found
		}

		if (newGraphNode < curr->m_graphNodeData) {
			return curr; // found position
		}
		after = curr;
		curr = curr->m_nextListNode; // move to next node on list
	}

	return curr; // return list's end
}

/***************************************************************************************
* function name: internalAdd(Node& newGraphNode, Node* before)
* The Input: Pointer to graph node to be added and a pointer to the list node where the
* 			 new graph node will be linked
* The output: None
* The Function operation: A new list node is created pointing to graph node to be added.
*			              Method links the new list node before the given list node and
*			              then increments next list nodes' indices
***************************************************************************************/
void NodeLinkedList::internalAdd(Node& newGraphNode, ListNode* before) {

	ListNode* newListNode = new ListNode(newGraphNode); // create a list node pointing to new graph node
	// link list node to list
	ListNode* prevListNodeBackup = before->m_prevListNode;
	newListNode->m_nextListNode = before;
	before->m_prevListNode = newListNode;

	newListNode->m_prevListNode = prevListNodeBackup;
	prevListNodeBackup->m_nextListNode = newListNode;

//	++(m_tailDummy->m_index); // increment tail's index
//	// update new list node's index
//	if (before == m_tailDummy) {
//		newListNode->m_index = m_tailDummy->m_index;
//	} else {
//		newListNode->m_index = before->m_index;
//	}
//	// increment index of next list nodes
//	while (before != m_tailDummy) {
//		before->m_index = (before->m_index)+1;
//		before = before->m_nextListNode;
//	}
}

//////////////////////////////////////////////////////////////////// public methods

/***************************************************************************************
* function name: NodeLinkedList()
* The Input: None
* The output: None
* The Function operation: List's head and tail are pointers to list nodes which do not point
*			              at graph nodes (point NULL). This implementation prevents the
*			              need to check if previous/next list nodes are NULL- makes code
*		                  more quick because there are less conditions to check
***************************************************************************************/
NodeLinkedList::NodeLinkedList() {

	// TODO DEBUG PRINT!!!
	cout << "in node linked list constructor" << endl;

	// create dummy list nodes at list's begging and end to avoid checking NULL values

	/* create graph nodes to be set as head and tail's graph node data
       the dummy graph nodes will be deleted in head and tail's destructors */
	Node& headDataDummy = *(new Node(NODE_DUMMY_INIT_VAL));
	Node& tailDataDummy = *(new Node(NODE_DUMMY_INIT_VAL));
	// set dummy graph nodes as head and tail's data
	m_headDummy = new ListNode(headDataDummy);
	m_tailDummy = new ListNode(tailDataDummy);

	// link head and tail
	m_headDummy->m_nextListNode = m_tailDummy;
	m_tailDummy->m_prevListNode = m_headDummy;

	// TODO DEBUG!!!
	m_currNode = m_headDummy;
}

/***************************************************************************************
 * function name: NodeLinkedList(const NodeLinkedList& listToCopy)
 * The Input: List to be copied
 * The output: None
 * The Function operation: Scans given lists, copies each node and link copy to new list
 ***************************************************************************************/
NodeLinkedList::NodeLinkedList(const NodeLinkedList& listToCopy) {

	// TODO DEBUG PRINT!!!
	cout << "in node linked list COPY constructor" << endl;

	// set new list's attributes as given list's
	m_headDummy = new ListNode(*listToCopy.m_headDummy);
	m_tailDummy = new ListNode(*listToCopy.m_tailDummy);

	// link head and tail
	m_headDummy->m_nextListNode = m_tailDummy;
	m_tailDummy->m_prevListNode = m_headDummy;

	// copy given list's nodes to new list

	ListNode* currListNode = m_headDummy; // list node pointer to previous node on new list
	ListNode* currOnGvnList = listToCopy.m_headDummy->m_nextListNode; // point to given list's first list node
	ListNode* currListNodeNextNodeBackp; // used to bakcup current node's on new list next node

	// scan given list to its end
	while (currOnGvnList != listToCopy.m_tailDummy) {

		currListNodeNextNodeBackp = currListNode->m_nextListNode; // backup current node's on new list next node
		currListNode->m_nextListNode = new ListNode(*currOnGvnList); // copy current node on given list
		// link new node to list
		currListNode->m_nextListNode->m_prevListNode = currListNode; // new node's previous node is current node on new list
		currListNode->m_nextListNode->m_nextListNode = currListNodeNextNodeBackp; // new node's next node is current node's on new list old next node
		currListNodeNextNodeBackp->m_prevListNode = currListNode->m_nextListNode; // current node's on new list old next node's previous node is new node

		currListNode = currListNode->m_nextListNode; // move to next node on new list
		currOnGvnList = currOnGvnList->m_nextListNode; // move to next node on given list
	}
}

/***************************************************************************************
* function name: ~NodeLinkedList()
* The Input: None
* The output: None
* The Function operation: Scans list from start to end and deletes each node
***************************************************************************************/
NodeLinkedList::~NodeLinkedList() {

	// TODO DEBUG PRINT!!!
	cout << "in node linked destructor" << endl;

	// scan list and delete list nodes
	ListNode* currNode = m_headDummy;
	ListNode* prevNode = m_headDummy;

	while (currNode != NULL) {
		// move to next node on list and delete the previous which has been scanned
		currNode = currNode->m_nextListNode;
		delete prevNode;
		prevNode = currNode;
	}
	delete prevNode; // delete last node on list
}

/***************************************************************************************
* function name: addNode(const Node& newGraphNode)
* The Input: Reference to graph node to be added
* The output: True if graph was added, False is not
* The Function operation: Method calls findPlace to find where the new graph node should
*			              be added. If no such place was found (returned value is NULL)
*		                  the method returns False. Otherwise, it calls internalAdd to
*			              add the new graph node to the list and returns True. New graph
*			              node is not changed
***************************************************************************************/
bool NodeLinkedList::addNode(const Node& newGraphNode) {

	ListNode* before = findPlace(newGraphNode); // find where, if any, graph node can be added

	// check if duplicate graph node was found
	if (before == NULL) {
		return false;
	}

	// create a copy of given node and the copy
	Node* graphNodeToAdd = new Node(newGraphNode);

	internalAdd(*graphNodeToAdd, before); // add graph node
	return true;
}
/***************************************************************************************
 * function name: removeListNode(const Node& nodeDataToRmv)
 * The Input: Reference to graph noder data whose list node should be removed
 * The output: True if removal was successful, False if not
 * The Function operation: Scans list and compares each list node's graph node data with
 * 						   given value. If a match is found, current list node and graph
 * 						   node data is deleted and True is returned. Otherwise, list is
 * 						   not changed and False is returned
 ***************************************************************************************/
bool NodeLinkedList::removeListNode(const Node& nodeDataToRmv) {

	ListNode* currListNode = m_headDummy->m_nextListNode; // point to first list node
	// scan list and search for a list node that holds given data
	while (currListNode != NULL) {
		if (currListNode->m_graphNodeData == nodeDataToRmv) { // match found, delete list node
			delete currListNode;
		}
		currListNode = currListNode->m_nextListNode; // match not found, move to next node
	}
	return false; // if reached here match was not found
}

/***************************************************************************************
 * function name: incrmntCurrNode()
 * The Input: None
 * The output: False if reached list's tail dummy node or if a next list node does
 * 			   not exist. Otherwise, returns true
 * The Function operation: Sets current node pointer to point at its next node.
 * 					       If the next node is NULL or list's dummy node, current node
 * 					       is not incremented and False is returned.
 * 					       Otherwise, current node pointer is incremented and True returned
 ***************************************************************************************/
bool NodeLinkedList::incrmntCurrNode() {

	if (m_currNode->m_nextListNode == m_tailDummy) { // reached list's end
		return false;
	}

	m_currNode = m_currNode->m_nextListNode; // has not reached end yet, move to next node
	return true;
}

/***************************************************************************************
 * function name: searchByKey(const Node& key)
 * The Input: Node (in graph) to look for
 * The output: Pointer to graph node that's equal to given key. If no such graph
 * 			   node exists, NULL is returned.
 * The Function operation: Scans list- if a match is found, a pointer to this graph node
 * 						   is returned. If not, NULL is returned.
 * 						   Method does not change list object
 ***************************************************************************************/
const Node* NodeLinkedList::searchByKey(const Node& key) const {

	ListNode* currListNode = m_headDummy->m_nextListNode; // pointer to first list node in list

	// scan graph's node list to its end
	while (currListNode != m_tailDummy) {

		// check if current graph node on list is equal to given key
		if (currListNode->m_graphNodeData == key) {
			// if they are equal, return pointer to current graph node
			return &(currListNode->m_graphNodeData);
		}

		// move to next node
		currListNode = currListNode->m_nextListNode;

	} // while (currListNode != m_tailDummy)

	// if reached here, key was not found- return NULL
	return NULL;
}

/***************************************************************************************
 * function name: searchByKey(const int& key)
 * The Input: Number to look for a graph node holding it
 * The output: Pointer to graph node that's equal to given key. If no such graph
 * 			   node exists, NULL is returned.
 * The Function operation: Scans list- if a match is found, a pointer to this graph node
 * 						   is returned. If not, NULL is returned.
 * 						   Method does not change list object
 ***************************************************************************************/
const Node* NodeLinkedList::searchByKey(const int& key) const {

	ListNode* currListNode = m_headDummy->m_nextListNode; // pointer to first list node in list

	// scan graph's node list to its end
	while (currListNode != m_tailDummy) {

		// check if current graph node on list is equal to given key
		if (int(currListNode->m_graphNodeData) == key) {
			// if they are equal, return pointer to current graph node
			return &(currListNode->m_graphNodeData);
		}

		// move to next node
		currListNode = currListNode->m_nextListNode;

	} // while (currListNode != m_tailDummy)

	// if reached here, key was not found- return NULL
	return NULL;

}

/***************************************************************************************
 * function name: <<
 * The Input: Reference to node liked list to be printed
 * The output: ostream reference
 * The Function operation: Scans list and prints nodes, using Node object's ostream
 * 			               operator. Braces are also printed.
 * 			               In order to follow node list's printing format, each node is
 * 			               converted to int and then printed
 ***************************************************************************************/
ostream& operator << (ostream &os, const NodeLinkedList& listToPrint) {

	// scan list and print each node
	cout << "|";
	NodeLinkedList::ListNode* currListNode = listToPrint.m_headDummy->m_nextListNode; // point to first node on list

	if (currListNode == listToPrint.m_tailDummy) { // list is empty, done printing
		return os << "|";
	}

	// if reached here, list is not empty
	cout << int(currListNode->m_graphNodeData); // print first node
	currListNode = currListNode->m_nextListNode; // move to next node on list

	while (currListNode != listToPrint.m_tailDummy) { // scan list to its end // TODO check if works
		cout << "," << int(currListNode->m_graphNodeData); // print current node
		currListNode = currListNode->m_nextListNode; // move to next node on list
	}

	// done printing the list
	return os << "|";
}

/***************************************************************************************
 * function name: incrementNodesValue()
 * The Input: None
 * The output: None
 * The Function operation: Scans list and uses graph node "++" operator to increment each
 * 					       graph node
 ***************************************************************************************/
void NodeLinkedList::incrementNodesValue() {
	ListNode* currListNode = m_headDummy->m_nextListNode; // point to list's start
	// scan list to its end
	while (currListNode != m_tailDummy) {
		++(currListNode->m_graphNodeData); // increment current graph node
		currListNode = currListNode->m_nextListNode; // move to next node on list
	}
}

/***************************************************************************************
 * function name: decrementNodesValue()
 * The Input: None
 * The output: None
 * The Function operation: Scans list and uses graph node "--" operator to decrement each
 * 					       graph node
 ***************************************************************************************/
void NodeLinkedList::decrementNodesValue() {
	ListNode* currListNode = m_headDummy->m_nextListNode; // point to list's start
	// scan list to its end
	while (currListNode != m_tailDummy) {
		--(currListNode->m_graphNodeData); // increment current graph node
		currListNode = currListNode->m_nextListNode; // move to next node on list
	}
}

/***************************************************************************************
 * function name: operator == (const NodeLinkedList& listOperand)
 * The Input: Graph node linked list to compare with
 * The output: True if all nodes are equal, False if not
 * The Function operation: Lists are sorted therefore both lists are scanned simultaneously
 * 						   and current nodes are compared. Once a mismatch was found,
 * 						   False is returned, otherwise True
 ***************************************************************************************/
bool NodeLinkedList::operator == (const NodeLinkedList& listOperand) const {

	// scan both list and compare nodes
	ListNode* currOnObject = m_headDummy->m_nextListNode; // point to object's start
	ListNode* currOnOperand = listOperand.m_headDummy->m_nextListNode; // point to operand's start

	// scan until one of list's end is reached
	while (currOnObject != m_tailDummy && currOnOperand != listOperand.m_tailDummy) {
		if (currOnObject->m_graphNodeData != currOnOperand->m_graphNodeData) {
			return false; // mismatch found, return False
		}
		// move to next node on both lists
		currOnObject = currOnObject->m_nextListNode;
		currOnOperand = currOnOperand->m_nextListNode;
	}

	// done scanning and did not find mismatch, lists are equal only if both of them reached their end
	return currOnObject == m_tailDummy && currOnOperand == listOperand.m_tailDummy;
}
